/*******************************************************************************
filename      SCVector.h
author        Craig Williams

Brief Description:
  CVector with sorting capabilities.

  This vector does not have to be sorted.

  functions:
    push_back()  - Adds a new elment to the end of the vector. This will break
                     the sort state.
    erase()      - Erases the specified element. If the vector is sorted, all
                     elements after the specified element will be shifted over.
                     Otherwise, the CVector erase is performed.
    insert()     - If the vector is sorted, a binary search is performed to
                     find the insertion spot, followed by shifting over all
                     the elements after that spot. If it is not sorted,
                     push_back() is used.
    sroted()     - Is the vector sorted?
    sort()       - Sorts the vector. If the vector is already sorted, this does
                     nothing. This uses quick sort.
    force_sort() - Forces the vector to sort. This is useful if one of the
                     elements changed within the vector that breaks the sort
                     order.

  search function: Linear Search if not sorted, binary otherwise.
    find_index() - Finds the index of the specified element in the vector.
                     ~0 if it is not found.
    find()       - Finds the specified element. NULL if not found.
    find_first() - Finds the first copy of the specified element.
                     NULL if not found.
    find_all()   - Finds all copies of the specified element.
*******************************************************************************/
#ifdef SCVECTOR_H    // Only compile if this file was included by SCVector.h

#include "CVectorHelpers.h"

/*******************************************************************************
   Function: SCVector()

Description: See Init()
*******************************************************************************/
template<typename T>
SCVector<T>::SCVector(int is, float growth,
                      bool (*les)(const T&, const T&)) : CVector<T>(is, growth)
{
  Sorted = 1;
  less   = les;
}

/*******************************************************************************
   Function: SCVector()

Description: See operator=
*******************************************************************************/
template<typename T>
SCVector<T>::SCVector(const SCVector<T> &vec) : CVector<T>(vec)
{
  Sorted = vec.Sorted;
  less   = vec.less;
}

/*******************************************************************************
   Function: operator=

Description: Makes a duplicate of another vector, includeing all the data
               that the specified vector contains.

     Inputs: &vec - Vector to duplicate

    Outputs: Refrence to the current vector
*******************************************************************************/
template<typename T>
SCVector<T> &SCVector<T>::operator=(const SCVector<T> &vec)
{
  static_cast<CVector<T> >(*this) = static_cast<CVector<T> >(vec);
  Sorted = vec.Sorted;
  less   = vec.less;
  return *this;
}

/*******************************************************************************
   Function: push_back()

Description: Adds a new element to the vector. This function will destory any
               sort order.

     Inputs: &data - Refrence to the data to add to the vector

    Outputs: N/A
*******************************************************************************/
template<typename T>
void SCVector<T>::push_back(const T &data)
{
  CVector<T>::push_back(data);
  Sorted = 0;
}

/*******************************************************************************
   Function: insert()

Description: Adds to a new element to the vector. If the vector is sorted, the
               sort will be preserved. If the vector isn't sorted, this function
               behaves like push_back()

     Inputs: &data - mData to add to the vector.

    Outputs: Refrence to the inserted data.
*******************************************************************************/
template<typename T>
T &SCVector<T>::insert(const T &data)
{
  int i;
  int left;
  int right;

  if(!Sorted)
  {
    CVector<T>::push_back(data);
    return CVector<T>::back();
  }

  if(CVector<T>::Cur == CVector<T>::Num)
    CVector<T>::AllocData();

  i     = 0;
  left  = 0;
  right = CVector<T>::Cur - 1;

  while(left <= right)
  {
    i = (left + right) >> 1;

    if(less(data, CVector<T>::mData[i]))
      right = i - 1;
    else
      left = ++i;
  }

  if(CVector<T>::Cur - i)
    CVectorMemmove(CVector<T>::mData + i + 1, CVector<T>::mData + i, sizeof(T) * (CVector<T>::Cur - i));

  new (CVector<T>::mData + i) T(data);
  ++CVector<T>::Cur;

  return CVector<T>::mData[i];
}

/*******************************************************************************
   Function: sorted()

Description: Returns true if the vector is sorted.

     Inputs: N/A

    Outputs: 1 - The vector is sorted
             0 - The vector is not sorted
*******************************************************************************/
template<typename T>
bool SCVector<T>::sorted(void) const
{
  return Sorted == 1;
}

/*******************************************************************************
   Function: sort()

Description: Sorts the data in the vector, using a quicksort. If the vector is
               already sorted, the function will do nothing.

     Inputs: N/A

    Outputs: N/A
*******************************************************************************/
template<typename T>
void SCVector<T>::sort(void)
{
  if(Sorted)
    return;

  force_sort();
}

#define Swap(a, b)                                                            \
{                                                                             \
  CVectorMemcpy(swap, CVector<T>::mData + (a), sizeof(T));                    \
  CVectorMemcpy(CVector<T>::mData + (a), CVector<T>::mData + (b), sizeof(T)); \
  CVectorMemcpy(CVector<T>::mData + (b), swap, sizeof(T));                    \
}

template<typename T>
void SortMedianOfThree(T *mData, int left, int right)
{
  unsigned char swap[sizeof(T)];
  int mid = (right + left) >> 1;

  if(mData[mid] < mData[left])
    Swap(left, mid);

  if(mData[right] < mData[mid])
  {
    Swap(mid, right);
    if(mData[mid] < mData[left])
      Swap(left, mid);
  }

  --right;
  Swap(right, mid);
}

template<typename F, typename T>
void InsertionSort(F less, T *mData, int size)
{
  unsigned char swap[sizeof(T)];
  int i, j;

  for(i = 1; i < size; ++i)
    for(j = i - 1; j >= 0; --j)
      if(less(mData[j + 1], mData[j]))
      {
        CVectorMemcpy(swap, mData + j, sizeof(T));
        CVectorMemcpy(mData + j, mData + j + 1, sizeof(T));
        CVectorMemcpy(mData + j + 1, swap, sizeof(T));
      }
      else
        break;
}

template<typename T>
void SCVector<T>::force_sort(void)
{
  /*
  unsigned char swap[sizeof(T)];
  int i, j;

  for(i = 1; i < (int)Cur; ++i)
    for(j = i - 1; j >= 0; --j)
      if(less(mData[j + 1], mData[j]))
      {
        CVectorMemcpy(swap, mData + j, sizeof(T));
        CVectorMemcpy(mData + j, mData + j + 1, sizeof(T));
        CVectorMemcpy(mData + j + 1, swap, sizeof(T));
      }
      else
        break;
  */

  unsigned char swap[sizeof(T)];
  unsigned char pivot[sizeof(T)];
  int    i, j;
  static CVector<int> stack;
  int    left = 0;
  int    right = CVector<T>::Cur;

  stack.RawSetCur(0);
  stack.push_back(0);
  stack.push_back(0);

  while(stack.size())
  {
    if(right - left <= 10)
    {
      if(right > left)
        InsertionSort(less, CVector<T>::mData + left, right - left);
      right = stack.back(); stack.pop_back();
      left  = stack.back(); stack.pop_back();
      continue;
    }

    i = left;
    j = right - 1;
/*
    {
      int mid = (i + j) >> 1;
      if(less(mData[mid], mData[i]))
        Swap(i, mid);
      if(less(mData[j], mData[mid]))
      {
        Swap(mid, j);
        if(less(mData[mid], mData[i]))
          Swap(i, mid);
      }
      Swap(j - 1, mid);
    }
    */
    CVectorMemcpy(pivot, CVector<T>::mData + j, sizeof(T));

    if(less(CVector<T>::mData[i], *reinterpret_cast<T*>(pivot)))
      for(++i; i < right && less(CVector<T>::mData[i], *reinterpret_cast<T*>(pivot)); ++i)
        {}
    if(!less(CVector<T>::mData[j], *reinterpret_cast<T*>(pivot)) && !(!less(CVector<T>::mData[j], *reinterpret_cast<T*>(pivot)) && !less(*reinterpret_cast<T*>(pivot), CVector<T>::mData[j])))
      for(--j; j > left  && !less(CVector<T>::mData[j], *reinterpret_cast<T*>(pivot)) && !(!less(CVector<T>::mData[j], *reinterpret_cast<T*>(pivot)) && !less(*reinterpret_cast<T*>(pivot), CVector<T>::mData[j])); --j)
        {}

    while(i < j)
    {
      Swap(i, j);
      while(++i < right  && less(CVector<T>::mData[i], *reinterpret_cast<T*>(pivot)))
        {}
      for(--j; j >  left && !less(CVector<T>::mData[j], *reinterpret_cast<T*>(pivot)) && !(!less(CVector<T>::mData[j], *reinterpret_cast<T*>(pivot)) && !less(*reinterpret_cast<T*>(pivot), CVector<T>::mData[j])); --j)
        {}
    }
    Swap(i, right - 1);

    if(i - left > right - i)
    {
      stack.push_back(left);
      stack.push_back(i);
      left = i;
    }
    else
    {
      stack.push_back(i);
      stack.push_back(right);
      right = i;
    }
  }

  Sorted = 1;
}

template<typename T>
void SCVector<T>::mark_unsorted(void)
{
  Sorted = 0;
}

/*******************************************************************************
   Function: erase()

Description: Removes the specified element from the vector. If the vector is
               sorted, the sort order will be preserved.

     Inputs: index - Numerical index of the item to remove

    Outputs: N/A
*******************************************************************************/
template<typename T>
void SCVector<T>::erase(unsigned int index)
{
  if(!Sorted)
    CVector<T>::erase(index);
  else
  {
    CVector<T>::mData[index].~T();
    --CVector<T>::Cur;
    if(CVector<T>::Cur - index)
      CVectorMemmove(CVector<T>::mData + index, CVector<T>::mData + index + 1, sizeof(T) * (CVector<T>::Cur - index));
  }
}

/*******************************************************************************
   Function: find()

Description: Searches through the vector, for the specfied item. If it's found,
               a pointer to the element will be returned. If not, a NULL pointer
               will be returned. If the vector is sorted, a binary search will
               be used.

     Inputs: &item - What to search for in the vector.

    Outputs: 0  - Item was not found
             1+ - Pointer to the element in the vector.
*******************************************************************************/
template<typename T>
unsigned int SCVector<T>::find_index(const T &item) const
{
  unsigned int i;

  if(Sorted)
  {
    int left = 0;
    int right = CVector<T>::Cur - 1;

    while(left <= right)
    {
      i = (left + right) >> 1;

      if(!less(CVector<T>::mData[i], item) && !less(item, CVector<T>::mData[i]))
        return i;
      else
      if(less(CVector<T>::mData[i], item))
        left = ++i;
      else
        right = i - 1;
    }
  }
  else
    for(i = 0; i < CVector<T>::Cur; ++i)
      if(!less(CVector<T>::mData[i], item) && !less(item, CVector<T>::mData[i]))
        return i;

  return ~static_cast<unsigned int>(0);
}

template<typename T>
T *SCVector<T>::find(const T &item) const
{
  unsigned int i = find_index(item);

  if(i == ~static_cast<unsigned int>(0))
    return 0;

  return CVector<T>::mData + i;
}

template<typename T>
T *SCVector<T>::find_first(const T &item) const
{
  CVector<T *> res = find_all(item);
  if(res.size())
    return res[0];
  return 0;
}

template<typename T>
CVector<T *> SCVector<T>::find_all(const T &item) const
{
  CVector<T *> out;

  unsigned int i;

  if(Sorted)
  {
    int left = 0;
    int right = CVector<T>::Cur - 1;

    while(left <= right)
    {
      i = (left + right) >> 1;

      if(!less(CVector<T>::mData[i], item) && !less(item, CVector<T>::mData[i]))
      {
        while(i - 1 != ~static_cast<unsigned int>(0) && !less(CVector<T>::mData[i - 1], item) && !less(item, CVector<T>::mData[i - 1]))
          --i;
        for(; !less(CVector<T>::mData[i], item) && !less(item, CVector<T>::mData[i]); ++i)
          out.push_back(CVector<T>::mData + i);
        return out;
      }
      else
      if(less(CVector<T>::mData[i], item))
        left = ++i;
      else
        right = i - 1;
    }
  }
  else
    for(i = 0; i < CVector<T>::Cur; ++i)
      if(!less(CVector<T>::mData[i], item) && !less(item, CVector<T>::mData[i]))
        out.push_back(CVector<T>::mData + i);

  return out;
}

#endif
